package com.github.yangyishe.p200;

import java.util.*;

/**
 * 127. 单词接龙
 * https://leetcode.cn/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150
 * todo 估计是图的构建过程不够优化
 *
 * 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
 *
 * 每一对相邻的单词只差一个字母。
 *  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
 *
 *
 * 示例 1：
 *
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：5
 * 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
 * 示例 2：
 *
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：0
 * 解释：endWord "cog" 不在字典中，所以无法进行转换。
 *
 *
 * 提示：
 *
 * 1 <= beginWord.length <= 10
 * endWord.length == beginWord.length
 * 1 <= wordList.length <= 5000
 * wordList[i].length == beginWord.length
 * beginWord、endWord 和 wordList[i] 由小写英文字母组成
 * beginWord != endWord
 * wordList 中的所有字符串 互不相同
 *
 */
public class Problem127 {
    public static void main(String[] args) {
        String beginWord = "hit", endWord = "cog";
        String[] wordList = new String[]{"hot","dot","dog","lot","log","cog"};

        Problem127 problem127 = new Problem127();
        int i = problem127.ladderLength(beginWord, endWord, Arrays.asList(wordList));
        System.out.println(i);

    }

    /**
     * 思路:
     * 将每个word看做是一个顶点, 当两个word只有一个字符差异, 则被视为边.
     * 所有的word就可以构建出一个无
     * 构建过程:
     * 时间复杂度O(n^2)
     *
     * 小优化: 在遍历word集合时, 如果始终没有发现endWord,可认为不存在
     *
     * 此后再使用广度优先遍历,使用minReachMap接收最短达到记录.
     * 参考广度优先的模板代码即可
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int wordLen=beginWord.length();
        Map<String,List<String>> word2WordListMap=new HashMap<>();
        word2WordListMap.put(beginWord,new ArrayList<>());
        for (String word : wordList) {
            List<String> linkWordList=new ArrayList<>();
            for (String oldWord : word2WordListMap.keySet()) {
                if(isNeighbor(word,oldWord)){
                    linkWordList.add(oldWord);
                }
            }
            word2WordListMap.put(word,linkWordList);
            for(String linkWord:linkWordList){
                word2WordListMap.get(linkWord).add(word);
            }
        }

        // 广度优先遍历
        Set<String> visited=new HashSet<>();
        Queue<String> queue=new LinkedList<>();

        visited.add(beginWord);
        queue.add(beginWord);

        Map<String,Integer> stepMap=new HashMap<>();
        stepMap.put(beginWord,1);

        while(!queue.isEmpty()){
            String word=queue.poll();
            int step=stepMap.get(word);

            // 打印

            List<String> nextWordList = word2WordListMap.get(word);
            for (String nextWord : nextWordList) {
                if(!visited.contains(nextWord)){
                    if(nextWord.equals(endWord)){
                        return step+1;
                    }
                    visited.add(nextWord);
                    queue.add(nextWord);
                    stepMap.put(nextWord,step+1);

                }
            }

        }


        return 0;
    }

    private boolean isNeighbor(String w1,String w2){
        int differSize=0;
        for(int i=0;i<w1.length();i++){
            if(w1.charAt(i)!=w2.charAt(i)){
                differSize++;
            }
            if(differSize>1){
                return false;
            }
        }
        return differSize==1;
    }
}
